#include "SortedList.h"
#include <cassert>
#include <iostream>
#include <typeinfo>

template <class T>
SortedList<T>::SortedList(bool reverse = false) {
    head = new ListNode<T>();
    end = head;
        
    if (reverse)
        compare = new GtCompare<T>();
    else
        compare = new LtCompare<T>();
}

template <class T>
void SortedList<T>::discard() {
    delete head;
    delete compare;
    compare = NULL;
    head = NULL;
    end = NULL;
}

// add elements in order defined by Compare
template <class T>
void SortedList<T>::add(const T& node) {
    if (head->nextp == NULL) {
        // insert in the beginning
        ListNode<T> *p = new ListNode<T>(node);
        head->nextp = p;
        end = p;
    }
    else if ((*compare)(end->node, node)) {
        // insert in the end
        ListNode<T> *p = new ListNode<T>(node);
        end->nextp = p;
        end = p;
    }
    else{
        ListNode<T> *pre = head;
        ListNode<T> *cur = pre->nextp;
        // slip
        while ( cur!=NULL && (*compare)(cur->node, node)) {
            pre = cur;
            cur = cur->nextp;
        }
        // add or insert 
        if (cur->node == node) {
            // just update old one, not insert
            cur->node += node;
        }
        else { 
            // insert in middle
            ListNode<T> *p = new ListNode<T>(node);
            pre->nextp = p;
            p->nextp = cur;
        }
    }
}

// remove all element equal to node
template <class T>
bool SortedList<T>::remove(const T& node) {
    bool flag = false;
    assert(head != NULL);
    for (ListNode<T>* it = head; it->nextp != NULL;) {
        if (it->nextp->node == node) {
            ListNode<T>* tmp = it->nextp;
            it->nextp = tmp->nextp;
            if (tmp == end) {
                end = it;
                delete tmp;
                return true;
            }
            delete tmp;
            flag = true;
        }
        else {
            it = it->nextp;
        }
    }
    return flag;
}

template <class T>
template <class Predicate>
void SortedList<T>::remove_if(Predicate pr) {
    for (ListNode<T>* it = head; it->nextp != NULL;) {
        if (pr(it->nextp->node)) {
            ListNode<T>* tmp = it->nextp;
            it->nextp = tmp->nextp;
            if (tmp == end) {
                end = it;
                delete tmp;
                return;
            }
            else {
                delete tmp;
            }
        }
        else { //move to next only when no delete action
            it = it->nextp;
        }
    }
}

// find the elements after p2(not contain) which is greater or equal to p1
// return a pointer before the found elements
template <class T>
ListNode<T>* SortedList<T>::find_ge(ListNode<T>* p2, ListNode<T>* pre1) {
    assert(p2 != NULL && pre1 != NULL && pre1->nextp != NULL );
    while (pre1->nextp != NULL && (*compare)(pre1->nextp->node, p2->node))
    pre1 = pre1->nextp;
    // until pre1< p2 < pre1->nextp or pre1->nextp == NULL(pre1 < p2)
    return pre1;
}

// combine li to this while keep order. li must has the same 'compare' with this
// if elements already exist in this, add it
// li will be discarded
template <class T>
void SortedList<T>::combine(SortedList<T>& li) {
    assert(typeid(*compare) == typeid(*(li.compare)));
    if(li.empty()) return;
    if(this->empty()) {
    head->nextp = li.head->nextp;
        end = li.end;
    }
    else {
    ListNode<T>* pre1 = head;
        ListNode<T>* p2 = li.head->nextp;
        while (p2 != NULL) {
    // search pre1 until: pre1 < p2 <= p1
    pre1 = find_ge(p2, pre1);
            ListNode<T>* p1 = pre1->nextp;
            pre1->nextp = p2;
        
            if (p1 != NULL && p1->node == p2->node) {
    p2->node += p1->node;
                // delete p1
                ListNode<T>* tmp = p1;
                p1 = p1->nextp;
                // maybe end
                if (tmp == li.end)
    li.end = NULL;
                else if (tmp == end)
    end = NULL;
                delete tmp;
            }
            // change search route
            pre1 = p2;
            p2 = p1;
        }
    
        // set end point, end maybe deleted or changed
        if (li.end!=NULL && (end == NULL || (*compare)(end->node, li.end->node))) {
    end = li.end;
        }
    }
    li.discard();
}

template <class T>
void SortedList<T>::print() {
    //    std::cout <<typeid(*compare).name() << std::endl;
    ListNode<T>* tmp = begin();
    while (tmp != NULL){
        std::cout<<tmp->node<<"\t";
        tmp = tmp->nextp;
    }
    std::cout<<std::endl;
}

template <class T>
SortedList<T>::~SortedList() {
    while (head != NULL){
        ListNode<T>* tmp = head;
        head = head->nextp;
        delete tmp;
    }
    if (compare != NULL)
        delete compare;
}

//test
class todelete {
  public:
    bool operator() (int a) { return a > 0;}
};
// test
int main() {
    SortedList<int> l1;
    l1.add(1);
    l1.add(4);
    l1.print();
    // to test
    SortedList<int> l2;
    l2.add(4);
    l2.add(2);
    l2.print();
    l1.combine(l2);
    l1.print();
    //    l1.remove(8);
    l1.remove_if( todelete() );
    l1.print();
}
